package real.bytedance.dfs_bfs;
import java.util.*;
import tree.TreeNode;

public class FindNodePath {
    
    public List<TreeNode> getNodePath(TreeNode root, TreeNode target) {
        if (root == null || target == null) return new ArrayList<>();
        return dfs(root, target, new LinkedList<>());
    }

    private List<TreeNode> dfs(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) {
            //这条路径没有目标节点
            return path;
        }
        if (root == target) {
            //当前节点为目标节点，将当前节点插到队尾
            path.add(0, root);
            return path;
        }
        //这里必须有个前提，target节点是唯一的，因此左右节点只有一个可以为path添加值
        List<TreeNode> left = dfs(root.left, target, path);
        List<TreeNode> right = dfs(root.right, target, path);
        if (!left.isEmpty()) {
            path = left;
        } else path = right;

        //若此时path不为空,队首添加路径
        if (!path.isEmpty()) path.add(0, root);
        return path;
    }
}
